The original problem is stated as follows:
\begin{align}
	z = \max \quad \sum_{i \in M} \sum_{j \in N} p_{ij} x_{ij} - \sum_{j \in N} f_j y_j & \\
	\sum_{j \in N} x_{ij} &= 1 & \forall i \in M \\
	x_{ij} & \le y_j & \forall i \in M, j \in N \label{ex5:linking} \\
	\vc{x} & \in \R_{\ge 0}^{|M| \times |N|} \\
	\vc{y} & \in \{0,1\}^{|N|} \label{ex5:yinteger}
\end{align}

The LP relaxation of this IP relaxes constraint~\eqref{ex5:yinteger} to $\vc{y} \in [0,1]^{|N|}$. The optimal LP relaxation value is $z^{\LP}$.

We dualize constraint~\eqref{ex5:linking} to arrive at the problem IP($\vc{u}$):

\begin{align}
	z(\vc{u}) = \max \quad \sum_{i \in M} \sum_{j \in N} \left( p_{ij} - u_{ij} \right) x_{ij}
		+ \sum_{j \in N} \left( \sum_{i \in M} u_{ij} - f_j \right) y_j & \\
	\sum_{j \in N} x_{ij} &= 1 & \forall i \in M \\
	\vc{x} & \in \R_{\ge 0}^{|M| \times |N|} \\
	\vc{y} & \in \{0,1\}^{|N|}
\end{align}

The value of the Lagrangian dual is $w_{\LD} = \min_{\vc{u} \ge \vc{0}} z(\vc{u})$. In general, $w_{\LD} \le z^{\LP}$. But in this case equality holds, as is evident by considering that

\begin{equation}
\conv \left( \{0,1\}^{|N|} \right) = [0,1]^{|N|}.
\end{equation}

This is sufficient because the only constraint that has not been dualized is the demand constraint and this constraint does not limit the integer variable $\vc{y}$. $\vc{x}$ does not have to be considered in the convex hull because it is real for the LP relaxation and the Lagrangian dual.

We can split the first double sum of $z(\vc{u})$ along the elements of $M$ and the second sum along the elements of $N$ to arrive at independent subproblems. We end up with the following problem description:

\begin{align}
	z(\vc{u}) &= \sum_{i \in M} z^1_i(\vc{u}) + \sum_{j \in N} z^2_j(\vc{u}) \\
	z^1_i(\vc{u}) &= \max_{\substack{\sum_{j \in N} x_{ij} = 1 \\ x_{ij} \ge 0}} \quad \sum_{j \in N} \left( p_{ij} - u_{ij} \right) x_{ij} & \forall i \in M \\
	z^2_j(\vc{u}) &= \max_{y_j \in \{0,1\}} \quad \left( \sum_{i \in M} u_{ij} - f_j \right) y_j & \forall j \in N \\
\end{align}

These problems can be solved easily by inspection:
\begin{align}
	z_i^1(\vc{u}) &= \max_{j \in N} (p_{ij} - u_{ij}) \\
	z_j^2(\vc{u}) &= \max \left\{\sum_{i \in M} u_{ij} - f_j, 0 \right\}
\end{align}